package union;

public class leetcode1643第K条最小指令 {
    public String kthSmallestPath(int[] destination, int k) {
        int hCount = destination[1];
        int vCount = destination[0];
        char[] str = new char[hCount + vCount];
        for (int i = 0; i < str.length; i++) {
            if (i < hCount) {
                str[i] = 'H';
            } else {
                str[i] = 'V';
            }
        }
        for (int i = 0; i < str.length; i++) {
            hCount--;
            int mod = unionCount(hCount, vCount);
            if (k > mod) {
                k -= mod;
                swap(str, i, i + hCount + 1 );
                vCount--;
                hCount++;
            }
            if (k == 1) {
                break;
            }
        }
        return new String(str);
    }
    
    public int unionCount(int num1, int num2) {
        if (num1 == 0) {
            return 1;
        }
        return (int) Math.ceil(mod(num1 + num2) / (mod(num2) * mod(num1)));
    }

    public void swap(char[] str, int i, int j) {
        char temp = str[i];
        str[i] = str[j];
        str[j] = temp;
    }
    
    public double mod(double n) {
        if (n == 0) {
            return 1;
        }
        return n * mod(n - 1);
    }
}
